[SW Expert Academy] 2105. 디저트 카페

Posted on July 12, 2021

문제 :

친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고

카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

디저트 카페 투어는 어느 한 카페에서 출발하여

[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다.

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.

<br/>

[ 제약 사항 ]

시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)
디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.

입력 :

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.

출력 :

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#t”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

풀이 :

카페 디저트 종류를 표현하고 있는 2차원 배열 map에서 그릴 수 있는 대각선 사각형 중 조건에 부합하는 가장 큰 사각형(칸을 가장 많이 지나가는 사각형)이 무엇인지 완전 탐색으로 찾아내는 문제이다.

문제에서 모든 사각형 경우의 수를 효율적으로 탐색할 수 있도록 구현하기 위해 몇 가지 KEY POINT를 설계했다.

[ KEY POINT ]

설계에서 가장 중요하게 설계한 포인트는 만들 수 있는 사각형의 너비(width), 높이(height) 제한 길이를 체크하고, 출발점에서 해당 너비, 높이 범위 내의 사각형을 그려가면서 같은 숫자가 없는지 판단하는 것이다.

해당 위치 인덱스에서 그릴 수 있는 사각형의 너비와 높이는 다음의 공식을 따른다.

int maxwidth = min(i, n - j); // 해당 인덱스에서 그릴 수 있는 최대 사각형 너비
int maxheight = min(n - j - curwidth, n - i) - 1;  // 해당 인덱스에서 그릴 수 있는 최대 사각형 높이

이렇게 최대 너비, 높이를 구하게 되면 해당 너비 높이 이하의 사각형들을 출발 위치에서 탐색하며 최대 디저트 종류 답을 도출해낸다.
사각형 탐색의 경우 대각선 방향을 순환하게끔 반복문으로 표현한 후 해당 너비, 높이만큼 대각선 방향 순서대로 탐색하며 사각형이 만들어질 때까지 중복되는 숫자가 나타나지 않는지 확인한다.

코드 :

코드 보기/접기

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
bool used[101];
int map[20][20], maxans, di[4] = {-1, 1, 1, -1}, dj[4] = {1, 1, -1, -1};

void init() {
    memset(used, false, sizeof(used));
}

void findMaxDesserts(int startx, int starty, int maxw, int maxh) {
    init();
    used[map[startx][starty]] = true;
    int curx = startx, cury = starty, cnt = 1;

    for (int k = 0; k < 4; k++) {
        int maxlen = (k % 2) ? maxh : maxw;

        for (int t = 0; t < maxlen; t++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k], cmpval = map[cmpx][cmpy];

            if (cmpx == startx && cmpy == starty) {
                maxans = max(maxans, cnt);
                return;
            }
            if (used[cmpval]) return;
            used[cmpval] = true;
            curx = cmpx;
            cury = cmpy;
            cnt++;
        }
    }
}

int testCase() {
    int n;
    maxans = -1;

    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int maxwidth = min(i, n - j);
            if (!maxwidth) continue;
            for (int curwidth = 1; curwidth <= maxwidth; curwidth++) {
                int maxheight = min(n - j - curwidth, n - i) - 1;
                if (maxheight < 1) break;
                for (int curheight = 1; curheight <= maxheight; curheight++)
                    findMaxDesserts(i, j, curwidth, curheight);
            }
        }
    return maxans;
}

int main(int argc, char **argv) {
    int test_case, T;

    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
        cout << '#' << test_case << ' ' << testCase() << '\n';
    return 0;
}

Algorithm

algorithm SW Expert C++